package com.week11;

import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;

public class HashDemo02 {
    private static final int VIRTUAL_NODE_NUM = 5;

    public String doSelect(final List<String> upstreamList, final String from_ip) throws Exception {
        final SortedMap<Long, String> treeMap = new TreeMap<>();
        for (String address : upstreamList) {
            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                long addressHash = hash("WEEK11-" + address + "HASH" + i);
                treeMap.put(addressHash, address);
            }
        }
        long hash = hash(String.valueOf(from_ip));
        SortedMap<Long, String> lastRing = treeMap.tailMap(hash);
        if (!lastRing.isEmpty()) {
            return lastRing.get(lastRing.firstKey());
        }
        return treeMap.get(treeMap.firstKey());
    }

    private static long hash(final String key){
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        // 如果算出来的值为负数则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }


}
